A lattice-theoretic framework is introduced that permits the study of theconditional independence (CI) implication problem relative to the class ofdiscrete probability measures. Semi-lattices are associated with CI statementsand a finite, sound and complete inference system relative to semi-latticeinclusions is presented. This system is shown to be (1) sound and complete forsaturated CI statements, (2) complete for general CI statements, and (3) soundand complete for stable CI statements. These results yield a criterion that canbe used to falsify instances of the implication problem and several heuristicsare derived that approximate this "lattice-exclusion" criterion in polynomialtime. Finally, we provide experimental results that relate our work to resultsobtained from other existing inference algorithms.
展开▼